/*
https://leetcode.cn/problems/number-of-islands/
*/
// 并查集 2
// T 为并查集节点的类型
template<typename T
> class DSU
{
    int group;      // 连通图的数量
    unordered_map<T, T> link_map;   // 根节点存储

    // 寻找一个给定节点的根节点，返回根节点的名称
    const T find_root(const T& node);
public:
    // 构造函数
    DSU();

    // 构造函数，传入参数为所有节点的名称
    DSU(vector<T>& nodes);

    // 析构函数
    ~DSU();

    // 合并两个节点
    void merge(const T& node_1, const T& node_2);

    // 判断两个节点的连通性，联通返回 true，否则返回 false
    bool link_check(const T& node_1, const T& node_2);

    // 插入一个节点
    void insert(const  T& node);

    // 返回并查集内连通图的数量
    int group_count() const;

    // 返回并查集内各个连通图的构成节点
    vector<vector<T>> all_group();
};

template<typename T
> DSU<T>::DSU() :
    group(), link_map()
{
    //
}

template<typename T
> DSU<T>::DSU(vector<T>& nodes) :
    group(nodes.size()), link_map()
{
    for (const auto& node : nodes)
    {
        link_map[node] = node;
    }
}

template<typename T
> DSU<T>::~DSU()
{
    //
}

template<typename T
> const T DSU<T>::find_root(const T& node)
{
    vector<T> nodes;    // 缩短距离

    T root = node;
    for (; link_map[root] != root; root = link_map[root])    // !(link_map[root] == root)
    {
        nodes.push_back(root);      // 缩短距离
    }

    // 缩短距离
    for (const auto& it : nodes)
    {
        link_map[it] = root;
    }

    return root;
}

template<typename T
>bool DSU<T>::link_check(const T& node_1, const T& node_2)
{
    if (link_map.find(node_1) == link_map.end() || link_map.find(node_2) == link_map.end())
    {
        return false;
    }
    return find_root(node_1) == find_root(node_2);
}

template<typename T
> void DSU<T>::merge(const T& node_1, const T& node_2)
{
    if (link_map.find(node_1) == link_map.end() || link_map.find(node_2) == link_map.end())
    {
        return;
    }

    //
    T root_1 = find_root(node_1), root_2 = find_root(node_2);
    if (root_1 != root_2)
    {
        --group;
    }
    link_map[root_2] = root_1;
}

template<typename T
> void DSU<T>::insert(const T& node)
{
    if (link_map.find(node) == link_map.end())
    {
        link_map[node] = node;

        ++group;
    }
}

template<typename T
> int DSU<T>::group_count() const
{
    return group;
}

template<typename T
> vector<vector<T>> DSU<T>::all_group()
{
    unordered_map<T, vector<T>> temp;
    for (auto& it : link_map)
    {
        T root = find_root(it.first);
        if (temp.find(root) == temp.end())
        {
            temp[root] = vector<T>();
        }
        temp[root].emplace_back(it.first);
    }

    vector<vector<T>> ans;
    for (auto& it : temp)
    {
        ans.emplace_back(it.second);
    }

    return ans;
}
class Solution {
public:
    DSU<string> dsu;

    string key(int a, int b) {
        string s = to_string(a) + " " + to_string(b);
        return s;
    }
    int numIslands(vector<vector<char>>& grid) {
        // 两边
        if (grid[0][0] == '1')
        {
            dsu.insert(key(0, 0));
        }
        for (int i = 1; i < grid[0].size(); ++i)
        {
            if (grid[0][i] == '1')
            {
                dsu.insert(key(0, i));
            }
            dsu.merge(key(0, i), key(0, i - 1));
        }
        for (int i = 1; i < grid.size(); ++i)
        {
            if (grid[i][0] == '1')
            {
                dsu.insert(key(i, 0));
            }
            dsu.merge(key(i, 0), key(i - 1, 0));
        }


        for (int t = 1; t < grid.size(); ++t)
        {
            for (int i = 1; i < grid[t].size(); ++i)
            {
                if (grid[t][i] == '1') {
                    dsu.insert(key(t, i));
                    dsu.merge(key(t, i), key(t, i - 1));
                    dsu.merge(key(t, i), key(t, i + 1));
                    dsu.merge(key(t, i), key(t - 1, i));
                    dsu.merge(key(t, i), key(t + 1, i));
                }
            }
        }
        return dsu.group_count();
    }
};